Stochastic compositional optimization arises in many important machine learning tasks such as reinforcement learning and portfolio management. The objective function is the composition of two expectations of stochastic functions, and is more challenging to optimize than vanilla stochastic optimization problems. In this paper, we investigate the stochastic compositional optimization in the general smooth non-convex setting. We employ a recently developed idea of \textit{Stochastic Recursive Gradient Descent} to design a novel algorithm named SARAH-Compositional, and prove a sharp Incremental First-order Oracle (IFO) complexity upper bound for stochastic compositional optimization: $\mathcal{O}((n+m)^{1/2} \varepsilon^{-2})$ in the finite-sum case and $\mathcal{O}(\varepsilon^{-3})$ in the online case. Such a complexity is known to be the best one among IFO complexity results for non-convex stochastic compositional optimization.

Neural Information Processing Systems http://nips.cc/

The other reviewers also convinced me that despite not having the right assumptions for the mention applications, the work might still be useful in other applications. I request the authors to remove the applications mentioned in the introduction or to explicitly write that their assumptions are not satisfied for them. Based on this points, I increase my score from 4 to 6. Let me also clarify on why I believe having the right assumption is important and what I dislike about the theory. SARAH is an interesting method as it does not require bounded gradients and, at the same time, there are settings where the its known complexity is better than that of SGD.

This paper has been deeply discussed between the reviewers and myself. After a lengthy discussion and thanks to the authors' rebuttal, the reviewers were convinced that the proposed algorithm and its analysis and novel, interesting, and worth to be published in NeurIPS. However, the reviewers also noted the mismatch between the motivating examples in the introduction and the assumptions in the analysis. Note that it is not enough to state that the assumptions hold in the "domain of optimization" because there is no guarantee that such domain is bounded. So, please carefully take into account the reviewers' comments in preparing the camera-ready version.

Stochastic compositional optimization arises in many important machine learning tasks such as reinforcement learning and portfolio management. The objective function is the composition of two expectations of stochastic functions, and is more challenging to optimize than vanilla stochastic optimization problems. In this paper, we investigate the stochastic compositional optimization in the general smooth non-convex setting. We employ a recently developed idea of \textit{Stochastic Recursive Gradient Descent} to design a novel algorithm named SARAH-Compositional, and prove a sharp Incremental First-order Oracle (IFO) complexity upper bound for stochastic compositional optimization: \mathcal{O}((n m) {1/2} \varepsilon {-2}) in the finite-sum case and \mathcal{O}(\varepsilon {-3}) in the online case. Such a complexity is known to be the best one among IFO complexity results for non-convex stochastic compositional optimization.

Stochastic compositional optimization arises in many important machine learning tasks such as reinforcement learning and portfolio management. The objective function is the composition of two expectations of stochastic functions, and is more challenging to optimize than vanilla stochastic optimization problems. In this paper, we investigate the stochastic compositional optimization in the general smooth non-convex setting. We employ a recently developed idea of \textit{Stochastic Recursive Gradient Descent} to design a novel algorithm named SARAH-Compositional, and prove a sharp Incremental First-order Oracle (IFO) complexity upper bound for stochastic compositional optimization: $\mathcal{O}((n m) {1/2} \varepsilon {-2})$ in the finite-sum case and $\mathcal{O}(\varepsilon {-3})$ in the online case. Such a complexity is known to be the best one among IFO complexity results for non-convex stochastic compositional optimization.